package com.learn.algorithm.graph;

public class LeetCode864 {
    public static int[] move = new int[]{-1, 0, 1, 0, -1};
    public static int MAXN = 31;
    public static int K = 6;

    public static char[][] grid = new char[MAXN][];

    public static boolean[][][] visited = new boolean[MAXN][MAXN][1 << K];

    // 格子的数量 * 扩点的数量
    // 0 行 1 列 2 收集到的钥匙的状态
    public static int[][] queue = new int[MAXN * MAXN * (1 << K)][3];

    public static int l, r, n, m, key;

    public static void build(String[] g) {
        l = r = key = 0;
        n = g.length;
        m = g[0].length();
        for (int i = 0; i < n; i++) {
            grid[i] = g[i].toCharArray();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '@') {
                    queue[r][0] = i;
                    queue[r][1] = j;
                    // 没有收集到任何钥匙
                    queue[r++][2] = 0;
                }
                // 发现钥匙时更新钥匙的状态
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
                    key |= 1 << (grid[i][j] - 'a');
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k <= key; k++) {
                    visited[i][j][k] = false;
                }
            }
        }
    }

    public int shortestPathAllKeys(String[] g) {
        build(g);
        int level = 1;
        while (l < r) {
            for (int k = 0, size = r - l, x, y, s; k < size; k++) {
                x = queue[l][0];
                y = queue[l][1];
                s = queue[l++][2];

                for (int i = 0; i < 4; i++) {
                    int toX = x + move[i];
                    int toY = y + move[i + 1];
                    int ns = s;

                    // 越界或是墙
                    if (toX < 0 || toX == n || toY < 0 || toY == m || grid[toX][toY] == '#') {
                        continue;
                    }
                    // 是锁头但又没有钥匙
                    if (grid[toX][toY] >= 'A' && grid[toX][toY] <= 'F' && (ns & (1 << grid[toX][toY] - 'A')) == 0) {
                        continue;
                    }
                    // 是钥匙 更新当前的钥匙状态
                    if (grid[toX][toY] >= 'a' && grid[toX][toY] <= 'f') {
                        ns |= (1 << (grid[toX][toY] - 'a'));
                    }
                    if (ns == key) {
                        return level;
                    }

                    if (!visited[toX][toY][ns]) {
                        visited[toX][toY][ns] = true;
                        queue[r++] = new int[]{toX, toY, ns};
                    }
                }
            }
            level++;
        }
        return -1;
    }
}
